COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00011 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A06.Tex[262,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, April 10, 1990}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Stirling Numbers: Reference}

We use $n\brace k$ and $n\brack k$ for the positive forms.  Define
$n\brace k$ as the number of partitions of ${\bf n}$ into $k$ subsets,
and $n\brack k$ as the number of permutations of $\bf n$ with $k$ cycles.

\noindent{\bf Recurrence Relations}

Partition ${n+1}\brace k$ by the placement of $n+1$ into one of
$k$ subsets of $n\brace k$, or as a new subset appended to
$n\brace {k-1}$;
$$\eqalign{{n+1\brace k} & = {n\brace k-1} + k{n\brace k}\cr
{0\brace k} & = [k=0]\cr}$$
Partition $n+1\brack k$ by the insertion of $n+1$ after one of $n$ elements
of cycles of $n\brack k$, or as a new unit cycle appended to
$n\brack k-1$;
$$\eqalign{{0\brack k}& = [k=0]\cr
{{n+1}\brack k} & = {n\brack {k-1}} + n {n\brack k}\cr}$$
\vskip 1.75in
${n\brace 0} = [n=0]$; ${n\brace 1} = [n>0]$; ${n\brace 2} =
(2↑{n-1}- 1)[n>0]$; ${n\brace n} = 1$; ${n\brace {n-1}} = {n\choose 2}$

Let $g↓n(z)$ be the row generating function 
$$\sum↓k{n\brace k} z↑k$$;
$$\eqalign {g↓0 & = 1\cr
g↓{n+1}& = z(g↓n + g'↓n)\cr}$$
Let $\gamma↓k$ be the column generating function $\sum↓n {n\brace k} w↑n$;
$$\gamma↓k  = z(k\gamma↓k + \gamma↓{k-1});$$
$$\gamma↓k  = {z\over {1-kz}}\gamma↓{k-1} = {1\over {1\over z} - k} \gamma↓{k-1}$$
$${1\over {\gamma↓k}} = \left ({1\over z}\right )\left ({1\over z}- 
1\right )\cdots \left ({1\over z}- (k-1)\right ) = \left ({1\over z}
\right )↑{\underline k}$$
$$\gamma↓k \left ({1\over z}\right ) = z↑{\underline k}$$
\vskip 1.75in
$${n\brack 0} = [n=0]; {n\brack 1} = (n-1)!\, [n>0]; {n\brack 2} = n!\, H↓n;
{n\brack n} = 1; {n\brack n-1} = {n\choose 2}$$
Let $h↓n(z)$ be $\sum↓k {n\brack k} z↑k$;
$$\eqalign{h↓0 & =1\cr
h↓{n+1} & = (n+z) h↓n\cr}$$
Then $h↓n = z↑{\overline n}$.
$$\sum↓k {n\brack k} = h↓n(1) = 1↑{\overline n} = n!,$$
the number of permutations.

We can use $n \brack k$ to express rising factorial polynomials as ordinary
polynomials by $z↑{\overline n} = h↓n(z) = \sum↓k {n\brack k} z↑k$.  Falling
powers are done by [RWF: needs work]
$$\eqalign{z↑{\underline n} & = \Pi (z-j) = \Pi - (-z+j) = 
(-)↑n(-z)↑{\overline n}\cr
& = (-)↑n h↓n(-z) = \sum↓k(-)↑{n+k} {n\brack k}z↑k.\cr}$$
So the signed Stirling numbers $(-)↑{n+k} {n\brack k}$ play a role dual to
$n\brack k$.  Maybe there should be a special symbol, ${n\brack k}↑-$,
laying a checkerboard of minus signs over the table of $n\brack k$.  Its 
(row) generating function is $h↑-↓n (z) = (-)↑n h↓n (-z) = (-)↑n 
(-z)↑{\overline n}= z↑{\underline n}$.
\smallskip
\noindent{\bf As Sums of Products}

Expanding $h↓n(z) = z(1+z)(2+z)\cdots((n-1)+z)$, the coefficient of $z↑k$ is a
sum of $n\choose k$ terms, each of which is a product of 
$k$ distinct numbers
from $[0, n)$.  Then ${n\brack k} = \sum [0\leq a↓1 < a↓2 <\cdots a↓k < n]
a↓1a↓2\cdots a↓k$.  By substituting $n+1$ for $n$, and case analysis on
$a↓k = n$, the recurrence relation reappears.

Similarly, ${n\brace k} = \sum [0\leq a↓1 \leq a↓2\cdots \leq a↓{n-k} <n]
a↓1a↓2\cdots a↓{n-k}$, because both satisfy the same recurrence.  The sum
$\sum [1\leq a↓1 < a↓2\cdots < a↓k \leq n] {1\over a↓1a↓2\cdots a↓k}$ can
be expressed with summand $b↓1b↓2\cdots b↓{n-k}\over n!$, giving the sum
${n+1\brack n-k}/n!$

We can expand ordinary powers in falling factorial powers by
$$x↑n = \sum↓k {n\brace k} x↑{\underline k}$$
The basis of the induction, at $n=0$, is $1=1$; the induction step is
$$\eqalign{x↑{n+1} & = \sum↓k {n\brace k} x↑{\underline k}((x-k)+k)\cr
& = \sum↓k {n\brace k} x↑{\underline {k+1}} + \sum↓k k{n\brace k} x↑
{\underline k}\cr
& = \sum↓k \left({n\brace k-1} + k{n\brace k}\right)x↑{\underline k}\cr
& = \sum↓k {n+1\brace k} x↑{\underline k}.\cr}$$
To expand in rising powers, use
$$\eqalign{x↑n & = (-)↑n(-x)↑n = (-)↑n \sum↓k {n\brace k} (-x)↑{\underline k}\cr
& = (-)↑n \sum↓k {n\brace k} (-)↑k x↑{\overline k}\cr
& = \sum↓k(-)↑{n+k}{n\brace k} x↑{\overline k}.\cr}$$
This suggests ${n\brace k}↑- = (-)↑{n+k}{n\brace k}$.  The column generating
function of ${n\brace k}↑-$ is $(-)↑n \gamma↓k(- w)$.  

Going from ordinary powers to rising powers and back gives:
$$\eqalign{x↑n & = \sum↓k(-)↑{n+k} {n\brace k} x↑{\overline k}\cr
& = \sum↓k(-)↑{n+k} {n\brace k} \sum↓j {k\brack j} x↑j\cr}$$
The coefficient of $x↑j$, which must equal $[j=n]$, is 
$\sum↓k (-)↑{n+k} {n\brace k}{k\brack j}$.

So, viewed as a linear transformation, $k\brack j$ has inverse 
${n\brace k}↑-$.

Similarly
$$\eqalign{x↑n & = \sum↓k {n\brace k} x↑{\underline k}\cr
& = \sum↓k {n\brace k} \sum↓j (-)↑{k+j} {k\brack j} x↑j,\cr}$$
so
$$\sum↓k {n\brace k}{k\brack j}↑- = [n=j],$$
and ${n\brace k}\hbox { has inverse } {k\brack j}↑-$

The diagram below summarizes:
$$x↑{\overline a}
\hskip 20pt
\matrix{\displaystyle{a\brack b}↑{\phantom{-}}\cr
\noalign{\vskip 20pt}
\displaystyle{b\brace a}↑-\cr}
\hskip 20pt
x↑b
\hskip 20pt
\matrix{\displaystyle{b\brace c}↑{\phantom{-}}\cr
\noalign{\vskip 20pt}
\displaystyle{c\brack b}↑-\cr}
\hskip 20pt
x↑{\underline c}$$
\end